1. Field of the Invention
This invention relates to computer graphics systems and, more particularly, to arrangements for more efficiently clipping polygons to lie within windows on computer output displays.
2. History of the Prior Art
Modern computer systems are able to process a plurality of programs at the same time. This is usually accomplished by the various programs running on a computer system essentially timesharing the facilities of central processing unit. When a plurality of programs are being run by a central processing unit at the same time, graphic output displays for each of the programs may be presented together on the computer output display in separate windows. A window in a two-dimensional computer output display is usually a rectangle which contains the graphic information for the particular program being displayed in that window. In any case, the information being displayed in a window is often less than the entire graphic presentation which is available; and it is necessary to clip the graphics image to fit within a particular output display.
Graphics figures are often described on an output display in the form of polygons. Usually the method of clipping a polygon to fit within a window requires that the lines joining the vertices of the polygon to be displayed be compared with the lines describing the window boundaries to determine which portions of the polygon lie within the window boundaries. A number of algorithms have been provided for accomplishing this comparison of lines joining the vertices of polygons with the computer boundaries. The most used of these algorithms, the Sutherland-Hodgman algorithm is described in a paper entitled "Re-entrant Polygon Clipping", Sutherland and Hodgman, Communications of the Association for Computing Machinery, Volume 17, No. 1, January, 1974. The Sutherland-Hodgman algorithm computes, for each window boundary a new polygon by clipping each of the sides of the "input " polygon against a particular window boundary. This produces an "output" polygon. This "output" polygon then becomes the "input" polygon for the next window boundary, producing a new "output" polygon. This sequence is repeated until all the window boundaries are scanned and the last "output" polygon will fit in the window. The implementation of the Sutherland-Hodgman algorithm requires a very substantial amount of memory and requires a significant amount of central processing unit time in order to accomplish its objects.
Since so much time and memory is required by the Sutherland-Hodgman algorithm, other algorithms have been suggested. Weiler and Atherton, in an article entitled "Hidden Surface Removal Using Polygon Area Sorting", published in the proceedings of Siggraph, 1977, pages 214-222, present an algorithm for polygon hidden surface and hidden line removal. The algorithm recursively subdivides the image into polygon-shaped windows until the depth order within the window is found. The algorithm is especially accurate but is so complex that it takes a great deal of computer time and memory to operate. Furthermore, the algorithm is not optimized for a rectangular window and, consequently, is relatively slow running.
Liang and Barsky, in an article entitled "An Analysis and Algorithm for Polygon Clipping", Communications of the ACM, November, 1983, Volume 26, pages 868-877, published an algorithm which speeds the operation of the Sutherland-Hodgman algorithm by approximately two times. Unlike the Sutherland-Hodgman algorithm and Liang and Barsky algorithm is limited to two dimensional and rectangular windows. The Liang and Barsky algorithm computes the intersections of a line which is a side of a polygon extended infinitely with all clip planes also extended infinitely. It then uses these intersections to determine points lying off the polygonal sides but necessary to be included within the clipped polygon (known as turning points or turning vertices). These points are the four corners of the clipped window which in the clipped polygon often becomes portions of the polygon to be presented. The Liang and Barsky algorithm, although faster than the Sutherland-Hodgman algorithm, requires the use of a substantial number of floating point computations which are difficult and very time consuming unless the particular computer system includes a floating point co-processor. Many microprocessor based computer systems do not include such a co-processor and the calculations with these machines are extremely complicated and time consuming.
Finally, Sutherland-Cohen devised a method for clipping lines only by quickly determining cases in which a particular line segment lies entirely within the clipping window and should be completely drawn and those in which a particular line segment lies entirely outside of the clipping window within a particular area in which it should not be drawn; see Newman and Sproull, Principles of Interactive Computer Graphics 2d. Ed., Mc Graw-Hill, pp. 65-69. These are referred to as trivial acceptance and trivial rejection cases and do not require the implementation f an entire intersection calculation. The Sutherland-Cohen algorithm provides a rapid method for determining these trivial acceptance and rejection cases and greatly speeds the implementation of a clipping algorithm. However, the Sutherland-Cohen algorithm does not provide a way of clipping polygons and, therefore, does not generate the additional intersections to determine points lying off the polygonal sides but to be included within the clipped polygon (turning points).